package class05;

public class Code01_MorrisTraversal {
	
	public static class Node {
		public int value;
		Node left;
		Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	/**
	 * Morris遍历
	 * @param head
	 */
	public static void morris(Node head) {
		if (head == null) {
			return;
		}
		Node cur = head;
		Node mostRight = null;
		while (cur != null) { // 过流程 -> 标准（3）
			mostRight = cur.left; // cur的左孩子给mostRight，用来判断是否有左子树

			if (mostRight != null) { // 有左子树
				while (mostRight.right != null && mostRight.right != cur) { // 因为左子树上最有孩子的右指针有两个状态，可能指向null，也可能指向当前节点cur
					mostRight = mostRight.right;
				}
				// mostRight变成了cur左子树上，最右的节点
				if (mostRight.right == null) { // 这是第一次来到cur
					mostRight.right = cur;
					cur = cur.left;
					continue;
				} else { // mostRight.right == cur
					mostRight.right = null;
				}
			}

			// 无左子树，if会被直接跳过
			cur = cur.right;
		}
		System.out.println();
	}



	/**
	 * 先序遍历
	 * @param head
	 */
	public static void morrisPre(Node head) {
		if (head == null) {
			return;
		}
		Node cur = head;
		Node mostRight = null;
		while (cur != null) { // 过流程 -> 标准（3）
			mostRight = cur.left; // cur的左孩子给mostRight，用来判断是否有左子树

			if (mostRight != null) { // 有左子树
				while (mostRight.right != null && mostRight.right != cur) { // 因为左子树上最有孩子的右指针有两个状态，可能指向null，也可能指向当前节点cur
					mostRight = mostRight.right;
				}
				// mostRight变成了cur左子树上，最右的节点
				if (mostRight.right == null) { // 这是第一次来到

					System.out.println(cur.value); //todo：可能出现两次的节点只打印第一次

					mostRight.right = cur;
					cur = cur.left;
					continue;
				} else { // 非第一次来到 mostRight.right == cur
					mostRight.right = null;
				}
			} else { // 没有左子树，说明该结点是叶子节点，只能出现一次
				System.out.print(cur.value + " "); //todo：只出现一次的节点直接打印
			}

			// 左边结束了，cur向右移动
			cur = cur.right;
		}
		System.out.println();
	}


	/**
	 * 中序遍历
	 * @param head
	 */
	public static void morrisIn(Node head) {
		if (head == null) {
			return;
		}
		Node cur = head;
		Node mostRight = null;
		while (cur != null) { // 过流程 -> 标准（3）
			mostRight = cur.left; // cur的左孩子给mostRight，用来判断是否有左子树

			if (mostRight != null) { // 有左子树
				while (mostRight.right != null && mostRight.right != cur) { // 因为左子树上最有孩子的右指针有两个状态，可能指向null，也可能指向当前节点cur
					mostRight = mostRight.right;
				}
				// mostRight变成了cur左子树上，最右的节点
				if (mostRight.right == null) { // 这是第一次来到自己
					mostRight.right = cur;
					cur = cur.left;
					continue;
				} else { // mostRight.right == cur
					mostRight.right = null;
				}
			}

			// 没有左子树的会跳过if，直接打印即可；
			// 对于能到达两次的节点，第一次continue直接回到while，碰不到打印行为；第二次跳出if可以碰到打印行为
			System.out.print(cur.value + " "); // todo：中序遍历只需要在这里加一条操作语句
			cur = cur.right;
		}
		System.out.println();
	}


	/**
	 * 后序遍历
	 * @param head
	 */
	public static void morrisPos(Node head) {
		if (head == null) {
			return;
		}
		Node cur = head;
		Node mostRight = null;
		while (cur != null) {
			mostRight = cur.left;
			if (mostRight != null) { // 有左子树
				while (mostRight.right != null && mostRight.right != cur) {
					mostRight = mostRight.right;
				}
				if (mostRight.right == null) { // 第一次来到自己，什么也不做
					mostRight.right = cur;
					cur = cur.left;
					continue;
				} else { // todo：后序遍历1 第二次来到自己时，逆序打印他左子树的右边界
					mostRight.right = null;
					printEdge(cur.left);
				}
			}
			// 无左子树，不用管
			cur = cur.right;
		}

		//todo：后序遍历2 整个循环结束后，单独打印整棵树的右边界
		printEdge(head);
		System.out.println();
	}


	// 以head为头的树，逆序打印这棵树的右边界
	public static void printEdge(Node head) {
		Node tail = reverseEdge(head);
		Node cur = tail;
		while (cur != null) {
			System.out.print(cur.value + " ");
			cur = cur.right;
		}
		reverseEdge(tail);
	}

	// 逆序右边界
	public static Node reverseEdge(Node from) {
		Node pre = null;
		Node next = null;
		while (from != null) {
			next = from.right;
			from.right = pre;
			pre = from;
			from = next;
		}
		return pre;
	}





	//------------------------Morris遍历的应用----------------
	/* 判断是否是搜索二叉树 */
	public static int preValue = Integer.MIN_VALUE;
	public static boolean isBSTByMorris(Node head) {
		if (head == null) {
			return true;
		}
		Node cur = head;
		Node mostRight = null;
		while (cur != null) { // 过流程 -> 标准（3）
			mostRight = cur.left; // cur的左孩子给mostRight，用来判断是否有左子树

			if (mostRight != null) { // 有左子树
				while (mostRight.right != null && mostRight.right != cur) { // 因为左子树上最有孩子的右指针有两个状态，可能指向null，也可能指向当前节点cur
					mostRight = mostRight.right;
				}
				// mostRight变成了cur左子树上，最右的节点
				if (mostRight.right == null) { // 这是第一次来到自己
					mostRight.right = cur;
					cur = cur.left;
					continue;
				} else { // mostRight.right == cur
					mostRight.right = null;
				}
			}

			// todo：操作语句，判断是否升序
			if(cur.value <= preValue) {
				return false;
			}
			preValue = cur.value;
			cur = cur.right;
		}
		return true;
	}
























	// for test -- print tree
	public static void printTree(Node head) {
		System.out.println("Binary Tree:");
		printInOrder(head, 0, "H", 17);
		System.out.println();
	}

	public static void printInOrder(Node head, int height, String to, int len) {
		if (head == null) {
			return;
		}
		printInOrder(head.right, height + 1, "v", len);
		String val = to + head.value + to;
		int lenM = val.length();
		int lenL = (len - lenM) / 2;
		int lenR = len - lenM - lenL;
		val = getSpace(lenL) + val + getSpace(lenR);
		System.out.println(getSpace(height * len) + val);
		printInOrder(head.left, height + 1, "^", len);
	}

	public static String getSpace(int num) {
		String space = " ";
		StringBuffer buf = new StringBuffer("");
		for (int i = 0; i < num; i++) {
			buf.append(space);
		}
		return buf.toString();
	}

	public static void main(String[] args) {
		Node head = new Node(4);
		head.left = new Node(2);
		head.right = new Node(6);
		head.left.left = new Node(1);
		head.left.right = new Node(3);
		head.right.left = new Node(5);
		head.right.right = new Node(7);
		printTree(head);
		morrisIn(head);
		morrisPre(head);
		morrisPos(head);
		printTree(head);

	}

}
